package HighMethod08;

/**
 * N皇后问题
 * 这里解决4后问题
 */
class NQueen {
    int n;      //皇后个数
    int[] x;    //一维数组模拟二维数组
    int sum;    //n个皇后的摆放方式数

    public NQueen(int n) {
        this.n = n;
        x = new int[n+1];         //开辟n个或者n+1个都行，循环控制的时候注意就好了
        sum = 0;
    }

    public int nQueen() {
//        BackTack(0);                      //递归的回溯
        BackTack();                         //没有递归的回溯
        return sum;
    }

    //递归放置皇后（也有回溯，但是不明显）
    private void BackTack(int t) {
        if (t >= n) {   //其实就是等于=
            sum++;
            PrintQ();   //第n个皇后可以放置说明这是一个可行的安置方案
        } else {
            for (int i = 0; i < n; i++) {
                x[t] = i;
                if (place(t)) {
                    BackTack(t + 1);
                }
            }
        }
    }

    //回溯明显来放置皇后
    private void BackTack() {
        int i = 1;
        x[i] = 0;
        while (i > 0) {
            x[i] += 1;
            while (x[i] <= n && !place(i)) {
                x[i] += 1;
            }
            if (x[i] <= n) {
                if (i == n) {
                    sum += 1;
                    PrintQ2();
                } else {
                    i++;
                    x[i] = 0;
                }
            }else {             //这里回溯
                i--;
            }
        }
    }


    private void PrintQ() {     //递归法的回溯的输出方法
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (x[i] == j) {      //如果第i个皇后再这想[i]列就输出@(代表皇后)
                    System.out.print("@");
                } else {
                    System.out.print("#");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
    private void PrintQ2() {            //回溯法的输出方法
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (x[i] == j) {      //如果第i个皇后再这想[i]列就输出@(代表皇后)
                    System.out.print("@");
                } else {
                    System.out.print("#");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    private boolean place(int t) {

        for (int i = 0; i < t; i++) {       //这里已经确定不是同一行，只需判断是否在同一列或者在对角线上
            if (x[i] == x[t] || (t - i) == Math.abs(x[t] - x[i])) {
                return false;
            }
        }

        return true;
    }

}

public class Queen {
    public static void main(String[] args) {

        int n = 4;
        NQueen nQueen = new NQueen(n);

        int sum = nQueen.nQueen();
        System.out.println(n + "个皇后的摆放方式种类数：" + sum);
    }
}
